/**
 * Created by ospip on 2018/3/22.
 * Copyright (c) 2018 LLAP. All rights reserved.
 */
import java.io.File;
import java.util.ArrayList;
import java.util.Scanner;
public class ThreadSort extends Thread {

    private int[] arr;
    private int low;
    private int high;
    private int depth;
    private static int maxDepth = 6;

    public ThreadSort(int[] arr, int low, int high, int depth) {
        this.arr = arr;
        this.low = low;
        this.high = high;
        this.depth = depth;
    }

    @Override
    public void run() {
        if (arr.length <= 0) return;
        if (low >= high) return;
        if (depth > maxDepth) return;
        System.out.println("Thread Created. (" + low + ", " + high + ", depth=" + depth + ")");
        qsort(low, high);

    }

    private void qsort(int low, int high){
        if (low < high){
            int pivot=partition(low, high);
            if (depth < maxDepth) {
                ThreadSort tl = new ThreadSort(arr, low, pivot - 1, depth + 1);
                ThreadSort tr = new ThreadSort(arr, pivot + 1, high, depth + 1);
                tl.start();
                tr.start();
                try {
                    tl.join();
                }
                catch (Exception ex) {
                    ex.printStackTrace();
                }
                try {
                    tr.join();
                }
                catch (Exception ex) {
                    ex.printStackTrace();
                }
            }
            else {
                qsort(low, pivot - 1);
                qsort(pivot + 1, high);
            }

        }
    }
    private int partition(int low, int high){
        int pivot = arr[low];
        while (low < high){
            while (low < high && arr[high] >= pivot) --high;
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot) ++low;
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }

    public static void main(String[] args) {
        int maxOutput = 20;

        Scanner in;
        try {
            in = new Scanner(new File("D:\\arrsort.txt"));
        }
        catch (Exception ex) {
            ex.printStackTrace();
            return;
        }

        ArrayList<Integer> lst = new ArrayList<>();

        while(in.hasNext()) {
            lst.add(in.nextInt());
        }
        in.close();
        System.out.println(lst.size());
        int[] arr = new int[lst.size()];
        for (int i = 0; i < lst.size(); i++) {
            arr[i] = lst.get(i);
        }
        for (int i = 0; i < arr.length && i <= maxOutput; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println();

        long startTime = System.currentTimeMillis();

        ThreadSort t = new ThreadSort(arr, 0, arr.length - 1, 1);
        t.start();
        try {
            t.join();
        }
        catch (Exception ex) {
            ex.printStackTrace();
        }

        long endTime = System.currentTimeMillis();

        for (int i = 0; i < arr.length && i <= maxOutput; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println();
        System.out.println(arr.length);
        System.out.println(String.format("%.5f ms", (double)(endTime - startTime) / 1000));
    }
}
